Stereo Matching Using Hierarchical Belief Propagation with GPU Acceleration

學生 ： 楊舜宇 陳彥廷

指導學長 ： 陳奕麟 金立軒

指導老師 ： 賴尚宏教授

1.前言:

Stereo Matching 是用左右兩台攝影機的影像來模擬雙眼，以左右兩張的影像來算出物體在空間中的深度。

Belief Propagation 是stereo algorithm 中的global method，比起local method有著比較好的結果但是比較慢的執行速度。Hierarchical Belief Propagation 是基於Belief Propagation的一種加速的方法，在Real-Time Global Stereo Matching Using Hierarchical Belief Propagation [1]的paper中達到了real time的速度。

2.目的:

這次專題的目的是將[1]的paper方法做加速，從原本用單一CPU所做的計算，把計算移到GPU上執行，以達到加速的效果。

3.實做方法:

程式流程圖:
 

各步驟說明:

1.讀入兩張要做stereo matching的圖：在這一步是讀入兩張相同大小PGM的灰階圖檔。

2.建立兩張圖的data cost：在這一步會建出一個3維的陣列，內容是存data cost，大小是width乘height乘disparity，width和height是讀入圖的寬和高，disparity是可能disparity的值。在CPU的程式是用三個for迴圈算出data cost，且time complexity為O(width*height*disparity)。而我們在GPU的版本是一次平行的算完一橫列的data cost，使得time complexity降到O(height*disparity)。
實做上在計算時把強度差不大的兩個點都當成是強度一樣的。

3.從最下層到最上層的建立data cost：在這一步會從前一步的data cost，建出一個長和寬都變為一半的3維陣列，內容是四個對應點的和，會一直重複這種動作直到最上層的data cost建好。

4. 用checkerboard的方式跑belief propagation來update message：在這一步用棋盤格的方式，交互地更新message。即每次都只有全部的一半的點的message會更新，且更新message的點的上下左右的message不會在同次更新，可以避免因為執行順序造成message的更新不一致。另外在實做上並沒有等到所有點的message真的都確定收斂才停止，而是固定一個iteration的次數t，獲得大部份點都收斂的結果。而在GPU的加速部分，因為沒有一個好的方法可以降低memory的存取次數，在這裡的加速是單純的同時計算四乘四或十六乘十六個點的message。

5.將message傳到下一層：在這一步會建出一個下層的message，大小是長和寬都變兩倍的3維陣列，內容是用上層的message當成對應的四個點的message，
在這一部分的沒有做GPU的加速部分，而是將4.的結果再傳回CPU去執行。

6.用現在最下層的message算出disparity：在這一步會找出每個點使energy function最小的disparity value，並且會將disparity value的值scale到255的強度範圍，以方便辨識。

7. output出一張深度大小的圖：在這一步是將6.的結果，寫成一個和讀入圖一樣大小的PGM檔。

4.結果:

執行環境:
CPU: AMD Phenom X4 9850 Black Edition
GPU: NVIDIA GeForce EN9800GT 512MB

1.執行時間:

2.output結果:

Tsukuba set:
     
CPU only                                      with GPU acceleration
     
Time: 1.242s                                    Time: 0.78s

Venus set:
       
CPU only                                            with GPU acceleration
       
Time: 2.274s                                            Time: 1.281s

Cones set:
     
CPU only                                            with GPU acceleration
     
Time: 6.441s                                            Time: 3.314s

Teddy set:
     
CPU only                                             with GPU acceleration
       
Time: 6.15s                                              Time: 3.228s

5.討論:

1.結果討論:

從CPU的結果來看，跑BP的步驟所花的時間約占總時間的75%，將message傳到下層的步驟占了約16%，可以說整個算HBP的部分占了90%以上。而GPU加速跑BP的步驟約加速了2到4倍左右，對於總時間理論上可以減少到一半左右。
將message傳到下層的步驟占了16%左右的時間有點意外，那一段程式並沒有做什麼算數運算的部分，只有new新的物件和把值傳入新物件之中。可能的原因應該是因為上下左右四個的三維message陣列所暫的memory實在太大，可能會用到100~200MB的儲存空間。在這個步驟可能可以經由不同的memory存取方法達到更好的效果，這部分涉及了compiler是否有做最佳化的部分，可能需要從assembly code來改進或是也用GPU來平行的同時存取memory。
從兩個表格的結果可以看到，在兩個步驟中所減少的時間並沒有全部都減少到完整的執行時間，有一些額外的時間因為用了GPU而增加。雖然不確定最主要的原因，不過可能是因為在GPU和CPU間因為會交互的執行指令，雖然在做GPU的運算時，CPU並沒有同時也在做運算，但是這段給CPU執行指令的時間依舊會浪費掉，導致結果不是很一致。

2.遇到的問題:

這次的專題有遇到一些問題，第一個是測試執行時間的問題。這個問題是關於CUDA在實際執行時，是可以讓CPU和GPU同時做不同的指令的。這裡會有一個問題會發生，就是如果是在CPU執行的時候去計算所執行的時間時，可能GPU實際上還在運作，測到的時間會不準。而在每個在GPU執行的function都算時間也不是個很好的方法，最後還是要各個相加，頻繁的計算時間也會把執行速度拖慢。
第二個問題是顯示卡架構下的各種memory都不大，而且計算能力每張顯示卡都不同。這使得不容易寫成一個最佳化的code，而且要寫出可以加速很多的code需要高階顯示卡的計算能力和夠多的記憶空間。

6.心得與感想:

在這個專題中學到了很多東西，像是CUDA programming和一些將演算法平行的策略等。而這個專題的結果應該還有進步的空間，像是把流程圖中第4步和第5步一起做加速，可以減少GPU和CPU之間的data傳輸，如果可以把花了90%時間的部分加速個4、5倍，結果可能會更明顯。

7.參考資料:

[1]Q. Yang, L. Wang, R. Yang, S. Wang, M. Liao and D. Nister, Real-Time Global Stereo Matching Using Hierarchical Belief Propagation, BMVC 2006.
[2] Pedro F. Felzenszwalb and Daniel P. Huttenlocher, Efficient Belief Propagation for Early Vision, Department of Computer Science, Cornell University.